package developer.算法.图论.腐烂的橘子;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;

/**
 * @author zhangyongkang
 * @time 2025/3/31 16:58
 * @description 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
 * <p>
 * 值 0 代表空单元格；
 * 值 1 代表新鲜橘子；
 * 值 2 代表腐烂的橘子。
 * 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
 * <p>
 * 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
 * <p>
 * <p>
 * <p>
 * 输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
 * 输出：4
 * 示例 2：
 * <p>
 * 输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
 * 输出：-1
 * 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。
 * 示例 3：
 * <p>
 * 输入：grid = [[0,2]]
 * 输出：0
 * 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
 */
public class FuLanDeJvZi {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] grid = {
                {2, 1, 1},
                {1, 1, 0},
                {0, 1, 1}
        };
        int i = solution.orangesRotting(grid);
        System.out.println("result = " + i);
    }

    static class Solution {

        public int orangesRotting(int[][] grid) {

            //记录初始烂橘子的位置
            Queue<int[]> badOriginQueue = new ArrayDeque<>();
            //记录好橘子的数量
            int fresh = 0;

            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                    int val = grid[i][j];
                    if (val == 2) {
                        badOriginQueue.offer(new int[]{i, j});
                    }
                    if (val == 1) {
                        fresh++;
                    }
                }
            }
            //开始进行腐烂
            int minutes = 0;
            while (!badOriginQueue.isEmpty()) {
                if(fresh<=0){
                    return minutes;
                }
                minutes++;
                int badSize = badOriginQueue.size();
                for (int i = 0; i < badSize; i++) {
                    int[] barOrange = badOriginQueue.poll();
                    int row = barOrange[0];
                    int col = barOrange[1];
                    //上下左右四个方向
                    //上
                    if (isInGrid(grid, row - 1, col)) {
                        int a = grid[row - 1][col];
                        if (a == 1) {
                            badOriginQueue.offer(new int[]{row - 1, col});
                            grid[row - 1][col] = 2;
                            fresh--;
                        }
                    }
                    //下
                    if (isInGrid(grid, row + 1, col)) {
                        int a = grid[row + 1][col];
                        if (a == 1) {
                            badOriginQueue.offer(new int[]{row + 1, col});
                            grid[row + 1][col] = 2;
                            fresh--;
                        }
                    }

                    //左
                    if (isInGrid(grid, row, col - 1)) {
                        int a = grid[row][col - 1];
                        if (a == 1) {
                            badOriginQueue.offer(new int[]{row, col - 1});
                            grid[row][col - 1] = 2;
                            fresh--;
                        }
                    }
                    //右
                    if (isInGrid(grid, row, col + 1)) {
                        int a = grid[row][col + 1];
                        if (a == 1) {
                            badOriginQueue.offer(new int[]{row , col+1});
                            grid[row][col + 1] = 2;
                            fresh--;
                        }
                    }
                }

            }
            if (fresh > 0) {
                return -1;
            }
            return minutes;
        }


        private boolean isInGrid(int[][] grid, int row, int col) {
            int maxRow = grid.length;
            int maxCol = grid[0].length;

            return row >= 0 && row < maxRow && col >= 0 && col < maxCol;
        }
    }

    class SolutionOther {
        public int orangesRotting(int[][] grid) {
            //1.定义2个int数组，2个一组来记录腐烂橘子的上下左右位置。腐烂橘子(0，0)
            //在矩阵中 上{-1,0}   下{1,0}  左{0,-1}   右{0,1}
            int[] dx = {-1, 1, 0, 0};
            int[] dy = {0, 0, -1, 1};
            int step = 0;//感染次数
            int flash = 0;//新鲜橘子数（后面用于判定是否为-1）

            int row = grid.length;//所给矩阵行
            int col = grid[0].length;//列

            Queue<int[]> queue = new ArrayDeque<>();
            //2.遍历矩阵 将所有的腐烂橘子入队，并且记录初始新鲜橘子数
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (grid[i][j] == 1) {
                        flash++;
                    }
                    if (grid[i][j] == 2) {
                        queue.offer(new int[]{i, j});
                    }
                }
            }

            //3.遍历所有腐烂橘子，同时感染四周
            while (flash > 0 && !queue.isEmpty()) {//有橘子且队列不空
                step++;
                //队列中现有的所有腐烂橘子都要进行一次感染
                int size = queue.size();
                for (int s = 0; s < size; s++) {
                    int[] poll = queue.poll();//腐烂橘子
                    for (int i = 0; i < 4; i++) {
                        //4个位置dx[i] dy[i]  ， xy 为要感染的橘子位置
                        int x = poll[0] + dx[i];//第x行
                        int y = poll[1] + dy[i];//第y列
                        if ((x >= 0 && x < row) && (y >= 0 && y < col) && grid[x][y] == 1) {
                            //xy不越界，并且要感染的地方是 新鲜橘子
                            grid[x][y] = 2;
                            //把被感染的橘子 入队
                            queue.offer(new int[]{x, y});
                            //新鲜橘子-1
                            flash--;
                        }
                    }
                }

            }

            //感染完了之后如果还有新鲜橘子
            if (flash > 0) {
                return -1;
            } else {
                return step;
            }
        }
    }


    class SolutionOfficial {
        int[] dr = new int[]{-1, 0, 1, 0};
        int[] dc = new int[]{0, -1, 0, 1};

        public int orangesRotting(int[][] grid) {
            int R = grid.length, C = grid[0].length;
            Queue<Integer> queue = new ArrayDeque<>();
            Map<Integer, Integer> depth = new HashMap<Integer, Integer>();
            for (int r = 0; r < R; ++r) {
                for (int c = 0; c < C; ++c) {
                    if (grid[r][c] == 2) {
                        int code = r * C + c;
                        queue.add(code);
                        depth.put(code, 0);
                    }
                }
            }
            int ans = 0;
            while (!queue.isEmpty()) {
                int code = queue.remove();
                int r = code / C, c = code % C;
                for (int k = 0; k < 4; ++k) {
                    int nr = r + dr[k];
                    int nc = c + dc[k];
                    if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2;
                        int ncode = nr * C + nc;
                        queue.add(ncode);
                        depth.put(ncode, depth.get(code) + 1);
                        ans = depth.get(ncode);
                    }
                }
            }
            for (int[] row : grid) {
                for (int v : row) {
                    if (v == 1) {
                        return -1;
                    }
                }
            }
            return ans;
        }
    }


}
